//快速排序，冒泡排序的改进
//冒泡排序是两两比较，快速排序两部分比较
//即，找一个基准值，将数据分成左右两部分
//对于左右两部分再重复上述操作

#include <iostream>

using namespace std;

void quickSort(int arr[] , int i_begin,int i_end)
{
    int baseValue = arr[i_begin];
    int low = i_begin;
    int high = i_end;

    /*
        1. 以首字母为基准，从右往左找high--，找到比首字母小的，放到首字母的位置
        2. low++，找到比基准大的数，放到high位置
        3. 判断low和high，low<high,重复1和2，否则结束
    */
    //递归退出条件
    if(i_begin>i_end)
    {
        return;
    }
    while(low<high)
    {
        //从右往左
        while(low<high && arr[high]>baseValue)
        {
            high--;
        }
        arr[low] = arr[high];
        while(low<high && arr[low]<baseValue)
        {
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = baseValue;

    //对基准左右序列，重复上述操作
    quickSort(arr,0,high-1);
    quickSort(arr,high+1,i_end);
}
int main()
{

    int arr[8] = {3,9,2,1,6,8,10,7};
    quickSort(arr,0,7);
    for(int i = 0;i<8;i++)
    {
        cout<<arr[i]<<",";
    }
    system("pause");
    return 0;
}
